"""
给定一个整数 n，返回 n 皇后不同的解决方案的数量。
https://leetcode-cn.com/problems/n-queens-ii/
"""


class Solution:
    def totalNQueens(self, n: int) -> int:

        row = [False for _ in range(n)]
        col = [False for _ in range(n)]
        hy1 = [False for _ in range(2 * n - 1)]  # 从右上到左下的斜边
        hy2 = [False for _ in range(2 * n - 1)]
        res = 0

        def dfs(i):
            nonlocal res
            if i == n:
                res += 1
                return
            for j in range(n):  # 循环列
                if (
                    not row[i]
                    and not col[j]
                    and not hy1[i + j]
                    and not hy2[i - j + n - 1]
                ):
                    row[i] = True
                    col[j] = True
                    hy1[i + j] = True
                    hy2[i - j + n - 1] = True
                    dfs(i + 1)
                    row[i] = False
                    col[j] = False
                    hy1[i + j] = False
                    hy2[i - j + n - 1] = False

        dfs(0)
        return res
